# Definition for a binary tree node.
from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        def find(root, target):
            if root is None:
                return False
            if root.val == target:
                return True
            elif root.val < target:
                return find(root.right, target)
            else:
                return find(root.left, target)

        def f(root):
            if root is None:
                return False
            find_v = target - root.val
            if find(root2, find_v):
                return True
            return f(root.left) or f(root.right)

        return f(root1)

    def twoSumBSTs2(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        def f(root, arr):
            if root is None:
                return
            f(root.left, arr)
            arr.append(root.val)
            f(root.right, arr)

        arr1, arr2 = [], []
        f(root1, arr1)
        f(root2, arr2)
        l, r = 0, len(arr2) - 1
        while l < len(arr1) and r >= 0:
            v = arr1[l] + arr2[r]
            if v == target:
                return True
            elif v < target:
                l += 1
            else:
                r -= 1
        return False

    # 生成器
    def twoSumBSTs3(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        def f1(root):
            if not root: return
            yield from f1(root.left)
            yield root.val
            yield from f1(root.right)

        def f2(root):
            if not root: return
            yield from f2(root.right)
            yield root.val
            yield from f2(root.left)

        a, b = f1(root1), f2(root2)
        try:
            v1, v2 = next(a), next(b)
            while True:
                v = v1 + v2
                if v == target:
                    return True
                elif v < target:
                    v1 = next(a)
                else:
                    v2 = next(b)
        except StopIteration:
            return False
